package leetcode.editor.cn;

class SearchA2dMatrixIi {
    public static void main(String[] args) {
        Solution solution = new SearchA2dMatrixIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // Z字形查找更快速
        // O（m + n）
        public boolean searchMatrix(int[][] matrix, int target) {
            int i = matrix.length - 1, j = 0;
            while (i >= 0 && j < matrix[0].length) {
                if (matrix[i][j] == target) return true;
                else if (matrix[i][j] > target) i--;
                else if (matrix[i][j] < target) j++;
            }

            return false;
        }

        // 二分也可以，对每一行进行二分

    }
//leetcode submit region end(Prohibit modification and deletion)

}
